import java.util.Deque;
import java.util.LinkedList;

/**
 * 430. 扁平化多级双向链表
 * https://leetcode-cn.com/problems/flatten-a-multilevel-doubly-linked-list/
 */
public class Solutions_430 {
    public static void main(String[] args) {
        Node_430 node1 = new Node_430(1);
        Node_430 node2 = new Node_430(2, node1);
        node1.next = node2;
        Node_430 node3 = new Node_430(3, node2);
        node2.next = node3;
        Node_430 node4 = new Node_430(4, node3);
        node3.next = node4;
        Node_430 node5 = new Node_430(5, node4);
        node4.next = node5;
        Node_430 node6 = new Node_430(6, node5);
        node5.next = node6;

        Node_430 node7 = new Node_430(7);
        Node_430 node8 = new Node_430(8, node7);
        node7.next = node8;
        Node_430 node9 = new Node_430(9, node8);
        node8.next = node9;
        Node_430 node10 = new Node_430(10, node9);
        node9.next = node10;

        Node_430 node11 = new Node_430(11);
        Node_430 node12 = new Node_430(12, node11);
        node11.next = node12;
        node3.child = node7;
        node8.child = node11;  // output: {1, 2, 3, 7, 8, 11, 12, 9, 10, 4, 5, 6}

//        Node_430 node1 = new Node_430(1);
//        Node_430 node2 = new Node_430(2);
//        Node_430 node3 = new Node_430(3);
//        node1.child = node2;
//        node2.child = node3;

        Node_430 result = flatten(node1);
        System.out.println(result);
    }

    /**
     * 解法二：迭代（0ms）
     */
    public static Node_430 flatten(Node_430 head) {
        Node_430 cur = head;
        // 通过栈实现迭代，利用 LinkedList 实现栈效果
        Deque<Node_430> stack = new LinkedList<>();
        while (cur != null) {
            if (cur.child != null) {
                // 有子链表
                if (cur.next != null) {
                    // 关键：后继节点不为 null，则后继节点入栈，供后续使用
                    stack.push(cur.next);
                }
                // 子链表头结点成为 cur 结点的后继结点
                cur.next = cur.child;
                cur.child.prev = cur;
                cur.child = null;
            }
            if (cur.next == null && !stack.isEmpty()) {
                // 关键：子链表迭代完成，从栈中取出进入子链表结点的后继结点
                Node_430 next = stack.pop();
                // 成为 cur 的后继结点
                cur.next = next;
                next.prev = cur;
            }
            cur = cur.next;
        }
        return head;
    }

    /**
     * 解法一：递归（1ms）
     */
    public static Node_430 flatten2(Node_430 head) {
        Node_430 cur = head;
        // 遍历链表
        while (cur != null) {
            if (cur.child != null) {
                // 临时记录 cur 下一节点，因为要对 cur 的下一节点重新赋值
                Node_430 next = cur.next;
                // 递归遍历子链表，返回链表
                Node_430 child = flatten(cur.child);
                // child 链表的头结点成为 cur 结点的后继结点，并将 cur.child 置空
                cur.next = child;
                child.prev = cur;
                cur.child = null;
                if (next != null) {
                    // cur 没有后继结点了，不需要再链接，next 结点成为 child 链表的后继结点
                    // 1. 找到 child 链表的结束结点
                    while (cur.next != null) {
                        cur = cur.next;
                    }
                    // 2. next 结点成为后继结点
                    cur.next = next;
                    next.prev = cur;
                }
            }
            cur = cur.next;
        }
        return head;
    }
}

class Node_430 {
    public int val;
    public Node_430 prev;
    public Node_430 next;
    public Node_430 child;

    public Node_430() {

    }

    public Node_430(int val) {
        this.val = val;
    }

    public Node_430(int val, Node_430 prev) {
        this.val = val;
        this.prev = prev;
    }

    public Node_430(int val, Node_430 prev, Node_430 next) {
        this.val = val;
        this.next = next;
        this.prev = prev;
    }
}
